package com.kaifamiao.linked;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class KfmLinkedList<E> implements List<E>{
	
	private static class Node<E> {
		E item ;
		Node<E> prev ;
		Node<E> next ;
		public Node(E item ) {
			super();
			this.item = item;
		}
	}
	
	private Node<E> head ; // 记录头节点的引用变量
	private Node<E> tail ; // 记录尾节点的引用变量
	
	private int counter ; // 记录元素个数的变量
	
	@Override
	public boolean add( E item ) {
		Node<E> node = new Node<E>( item );
		if( head == null ) { // 意味着是第一次添加元素
			head = node ; // 以新节点为头节点
		} else if( tail == null ) { // 意味着目前只有一个元素(只有头元素尾部元素尚未指定)
			tail = node ; // 以新节点为尾节点
			head.next = node ; // 让头结点指向尾节点
			node.prev = head ; // 以头节点为前驱节点
		} else { // 既指定了头节点也指定了尾节点
			tail.next = node ; // 1、让原来的尾节点指向新的节点
			node.prev = tail ; // 2、以原来的尾节点为前驱节点
			tail = node ; // 3、以新节点为新的尾节点
		}
		counter++ ; // 每添加成功一个则让counter自增一
		return true ;
	}
	
	@Override
	public int size() {
		return counter ;
	}
	
	@Override
	public boolean isEmpty() {
		return this.counter == 0 ;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append( '[' );
		
		Node<E> node = head ;
		while( node != null ) {
			sb.append( node.item );
			sb.append( ',' );
			node = node.next ;
		}
		int last = sb.lastIndexOf( "," );
		if( last != -1 ) {
			sb.deleteCharAt( last );
		}
		sb.append( ']' );
		return sb.toString();
	}
	
	@Override
	public void clear() {
		this.head = null ;
		this.tail = null ;
		this.counter = 0 ;
	}

	@Override
	public E get(int index) {
		int count = 0 ; // 下标从零开始计数
		Node<E> node = head ;
		while( node != null ) {
			if( count == index ) {
				return node.item ;
			}
			node = node.next ;
			count++ ;
		}
		return null;
	}
	
	@Override
	public boolean remove(Object o) {
		Node<E> node = head ;
		while( node != null ) {
			E item = node.item ;
			if( item == o || ( item != null && item.equals( o ) ) ) {
				// 未实现的: 如果被删除节点是头结点 或 尾节点应该如何处理
				node.prev.next = node.next ; // 让前一个节点的next指针指向当前节点下一个节点
				node.next.prev = node.prev ; // 让下一个节点的prev指针指向当前节点前一个节点
				counter-- ;
				return true ;
			}
			node = node.next ;
		}
		return false;
	}

	@Override
	public boolean contains(Object o) {
		return false;
	}

	@Override
	public Iterator<E> iterator() {
		return null;
	}

	@Override
	public Object[] toArray() {
		return null;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		return null;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		return false;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		return false;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		return false;
	}

	@Override
	public E set(int index, E element) {
		return null;
	}

	@Override
	public void add(int index, E element) {
	}

	@Override
	public E remove(int index) {
		return null;
	}

	@Override
	public int indexOf(Object o) {
		return 0;
	}

	@Override
	public int lastIndexOf(Object o) {
		return 0;
	}

	@Override
	public ListIterator<E> listIterator() {
		return null;
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		return null;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		return null;
	}
	
	

}
